package Hot100;

/**
 * @author zhangmin
 * @create 2021-12-20 14:09
 */
public class isMatch10 {
    /**10. 正则表达式匹配
     * 给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。'.' 匹配任意单个字符,'*' 匹配零个或多个前面的那一个元素
     * s[i]和p[j]可以匹配上：s[i]==p[j] 或者p[j]='.'
     *   1.1 p[j+1]是'*' ，考虑是匹配多次（i++，j不变）或者0次（i不变，j+2）
     *   1.2 p[j+1]不是'*'，只能直接匹配，i++，j++
     * s[i]和p[j]不相等，不能匹配到
     *   2.1 p[j+1]是‘*’,匹配0次，j+2，i不变
     *   2.2 p[j+1]不是‘*’ 匹配失败，直接返回false
     * */
    boolean isMatchij(String s,int i,String p,int j){
        int m=s.length(),n=p.length();
        if (j==n){
            //p到最后一位，判断s是否也匹配完成
            return i==m;
        }
        if (i==m){
            //s匹配完成，判断p是否可以匹配空串
            if ((n-j)%2==1) return false;
            for (int k = j+1; k < n; k+=2) {
                if (p.charAt(k)!='*') return false;
            }
            return true;
        }
        boolean res=false;
        if (s.charAt(i)==p.charAt(j)||p.charAt(j)=='.'){
            if (j<n-1&&p.charAt(j+1)=='*'){
                res=isMatchij(s,i+1,p,j)||isMatchij(s,i,p,j+2);
            }else {
                res=isMatchij(s,i+1,p,j+1);
            }
        }else {
            if (j<n-1&&p.charAt(j+1)=='*'){
                res=isMatchij(s,i,p,j+2);
            }else {
                res=false;
            }
        }
        return res;
    }

    public boolean isMatch(String s, String p) {
        return isMatchij(s,0,p,0);
    }
}
